10331. Отгадай животное
Когда коровам наскучила игра в “ракушки”, Бесси и её подруга Элси любят
развлекаться другой игрой – “угадай животное”.
Сначала Бесси загадывает какое-то
животное (чаще всего это, конечно, корова, что делает игру довольно скучной, но
иногда Бесси проявляет изобретательность и выбирает кого-то другого). Затем
Элси задаёт серию вопросов, чтобы выяснить, какое именно животное загадала
Бесси. Каждый вопрос касается наличия у животного определённого признака, а
Бесси отвечает на него “да” или “нет”. Например:
Elsie: "Животное летает?"
Bessie : "нет"
Elsie : "Животное ест траву?"
Bessie : "да"
Elsie : "Животное даёт молоко?"
Bessie : "да"
Elsie : "Животное говорит 'муу'?"
Bessie : "да"
Elsie : "В таком случае, думаю, это
корова."
Bessie : "Правильно!"
Назовём допустимым множеством
набор всех животных, характеристики которых согласуются с ответами Бесси на
вопросы Элси. Элси продолжает задавать вопросы до тех пор, пока в допустимом
множестве не останется ровно одно животное, после чего она объявляет его своим
ответом.
При этом каждый новый вопрос Элси
формулирует, выбирая характеристику какого-либо животного из текущего
допустимого множества – даже если этот вопрос не
обязательно поможет ей сузить выбор в дальнейшем. Она никогда не задаёт вопрос
о одной и той же характеристике дважды.
Зная всех животных, которых знают
Бесси и Элси, а также их характеристики, определите максимальное количество
ответов “да”, которые Элси могла бы получить до того, как угадает правильное животное.
Вход. Первая строка содержит
количество животных n (2 ≤ n ≤ 100).
Каждая из следующих n строк описывает одно животное. Строка начинается с
имени животного, за которым следует целое число k (1 ≤ k
≤ 100) – количество его характеристик, а затем перечисляются сами
характеристики.
Имена животных и характеристики
представляют собой строки из строчных латинских букв (a .. z)
длиной не более 20. Не существует двух животных с полностью совпадающими
наборами характеристик.
Выход. Выведите одно число – максимальное
количество ответов “да”, которое Элси могла бы получить до окончания игры.
|
Пример
входа |
Пример
выхода |
|
4 bird 2 flies
eatsworms cow 4 eatsgrass
isawesome makesmilk goesmoo sheep 1 eatsgrass goat 2 makesmilk
eatsgrass |
3 |
перебор
Перебором найдем
двух животных с максимальным количеством общих признаков temp. Тогда максимальное количество
ответов “да”, которые может получить Элси, равно temp + 1.
Пример
Корова и коза
имеют два общих признака: makesmilk, eatsgrass. На эти запросы Элси даст ответ “да”. Третьим запросом с ответом “да”
будет запрос о признаке коровы, отличный от этих двух.
Реализация алгоритма
Характеристики животного номер i будем хранить в массиве ch[i].
vector<string> ch[100];
Функция common вычисляет количество общих признаков
для животных с номерами i и j.
int common(int i, int j)
{
int cnt = 0;
for (int x = 0; x < ch[i].size(); x++)
for (int y = 0; y < ch[j].size(); y++)
if (ch[i][x] == ch[j][y]) cnt++;
return cnt;
}
Основная часть программы. Читаем входные данные.
cin >> n;
for (i = 0; i < n; i++)
{
cin >> s >> k;
for (j = 0; j < k; j++)
{
cin >> s;
ch[i].push_back(s);
}
}
Перебираем все пары животных. Для каждой пары (i, j)
вычисляем количество их общих признаков temp. Среди всех
таких значений temp вычисляем наибольшее значение res.
res = 0;
for (i = 0; i < n; i++)
for (j = i + 1; j < n; j++)
{
temp = common(i, j);
if (temp > res) res =
temp;
}
Выводим ответ.
cout << res + 1
<< endl;